MOPA

Model-theoretic frameworks for nonstandard methods require the existence of nonprincipal ultrafilters over N, a strong form of the Axiom of Choice (AC). While AC is instrumental in many abstract areas of mathematics, its use in infinitesimal calculus or number theory should not be necessary.

In the paper KH and M. G. Katz, Infinitesimal analysis without the Axiom of Choice, Ann. Pure Applied Logic 172, 6 (2021), https://arxiv.org/abs/2009.04980, we have formulated SPOT, a theory in the language that has, in addition to membership, a unary predicate 'is standard.' The theory extends ZF by three simple axioms, Transfer, Nontriviality and Standard Part, that reflect the insights of Leibniz. It is a subtheory of the nonstandard set theories IST and HST, but unlike them, it is a conservative extension of ZF. Arguments carried out in SPOT thus do not depend on any form of AC. Infinitesimal calculus can be developed in SPOT. A stronger theory SCOT is a conservative extension of ZF + Dependent Choice. It is suitable for handling such features as an infinitesimal approach to the Lebesgue measure.

Renling Jin recently gave a groundbreaking nonstandard proof of Szemeredi's theorem in a model-theoretic framework that has three levels of infinity. I will formulate and motivate SPOTS, a multi-level version of SPOT, carry out Jin's proof of Ramsey's theorem in SPOTS, and discuss how his proof of Szemeredi's theorem can be developed in it.

While it is still open whether SPOTS is conservative over ZF, SCOTS (the multi-level version of SCOT) is a conservative extension of ZF + Dependent Choice.

Slides

Video

​

As famously shown by Scott, every countable structure can be characterized, up to isomorphism, by a sentence of infinitary language $L_{\omega_1, \omega}$ which allows for conjunctions and disjunctions over arbitrary countable families of formulae (over finitely many variables). Formulae of this language can be naturally assigned ranks based on the number of alternations of existential connectives (disjunctions and existential quantifiers) with universal ones (conjunctions and universal quantifiers). This gives rise to a natural complexity measure for countable models: the Scott rank of a model $\mathcal{M}$ is the least $\alpha$ such that $\mathcal{M}$ can be uniquely characterized by a sentence of rank $\alpha+1$ (and starting from the universal quantifier). The developments of computable model theory witness that the Scott rank is a very robust notion integrating other well established tools from descriptive set theory, model theory and computability.

In 'The Structural Complexity of Models of Arithmetic' Antonio Montalban and Dino Rossegger pioneered the Scott analysis of models of Peano Arithmetic. They characterized the Scott spectrum of completions PA , i.e. the set of ordinals which are Scott ranks of countable models of a given completion $T$ of PA. A particularly intriguing outcome of their analysis is that PA has exactly one model of the least rank, the standard model, and the Scott rank of every other model is infinite. Additionally they studied the connections between Scott ranks and model-theoretical properties of models, such as recursive saturation and atomicity, raising an open question: is there a non-atomic homogeneous model of PA of Scott rank $\omega$?

In the talk we answer the above question to the negative, showing that the nonstandard models of PA or rank $\omega$ are exactly the nonstandard prime models. This witness another peculiar property of PA: not only it has the simplest model, but also its every completion has a unique model of the least Scott rank. This is joint work with Patryk Szlufik.

Video

​

There has been a long tradition in the model theory of arithmetic of attributing the combinatorial properties of cardinal numbers in set theory to initial segments. Considering that the most basic use of cardinal numbers is to assign cardinality to sets, we can adapt a similar notion in models of arithmetic in the following way: for a given initial segment $I$ of any model $\mathcal M$ of a fragment of arithmetic, say I$\Sigma_1$, a subset $X $ of $\mathcal M$ is called I-small if there exists a coded bijection $f$ in $\mathcal M$ such that the range of the restriction of $f$ to $I$ is equal to $X$. It turns out that for a given countable nonstandard model $\mathcal M$ of I$\Sigma_1$, when I is a strong cut, any $I$-small $\Sigma_1$-elementary submodel of $\mathcal M$ contains $I$, and inherits some good properties of $I$. In this talk, we are going to review such properties through self-embeddings of $\mathcal M$.

Slides

Video

​

Compared with end extensions, much little is known about cofinal extensions for models of fragments of PA, especially their elementarity. In this talk, I will try to give a complete characterization of the elementarity of cofinal extensions. I will present a systematic way to `compress' the truth of M into the second-order structure of a definable cut, and as a consequence, a correspondence theorem between the first-order theory of M and the second-order theory of the cut. Through this method I will construct several models with special cofinal extension properties. I will also show that every countable model of arithmetic fail to satisfy PA admits a non-elementary cofinal extension. It provides a model-theoretic characterization for PA in terms of cofinal extensions.

Video

​

This talk is about the relationship between (weak) arithmetical theories and methods for automated inductive theorem proving. Automating the search for proofs by induction is an important topic in computer science with a history that stretches back decades. A variety of different approaches, algorithms and implementations has been developed.

In this talk I will present a logical approach for understanding the power and limits of methods for automated inductive theorem proving. A central tool are translations of proof systems that are intended for automated proof search into weak arithmetical theories. Another central tool are non-standard models of these weak arithmetical theories.

This approach allows to obtain independence results which are of practical interest in computer science. It also gives rise to a number of new problems and questions about weak arithmetical theories.

Video

​

In 1994 Jech gave a model theoretic proof of Gödel's second incompleteness theorem for Zermelo-Fraenkel set theory in the following form: ZF does not prove that ZF has a model. Kotlarski showed that Jech's proof can be adapted to Peano Arithmetic with the role of models being taken by complete consistent extensions. In this note we take another step in the direction of replacing proof-theoretic by model-theoretic arguments. We show, without passing through the arithmetized completeness theorem, that the existence of a model of PA of complexity $\Sigma^0_2$ is independent of PA, where a model is identified with the set of formulas with parameters which hold in the model. Our approach is based on a new interpretation of the provability logic of Peano Arithmetic with the modal operator interpreted as truth in every $\Sigma^0_2$-model.

Slides

Video

​

We will discuss the following claim: 'The standard cut of a model $M$ of PA (or even Q) is uniformly definable with respect to a randomly chosen predicate.' Restricting our consideration to countable models, this claim is true in the usual sense, i.e. there is a formula $\varphi$ such that for any countable model of arithmetic $M,$ the set $S_M^{\varphi} := \{P \subset M: \omega = \{x \in M: (M, P) \models \varphi(x)\} \}$ is Lebesgue measure 1. However, if $M$ is countably saturated, then there is no $\varphi$ such that $S_M^{\varphi}$ is measured by the completed product measure on $2^M.$ We will identify various combinatorial ideals on $2^M$ that can be used to formalize the original claim with no restriction on the cardinality of $M,$ and discuss the relationship between closure properties of these ideals and principles of choice.

Video

​